function mergeSort(arr) {
  let len = arr.length
  if (len < 2) return arr
  let mid = Math.floor(len / 2)
  // console.log('mid', mid)
  let left = arr.slice(0, mid)
  let right = arr.slice(mid)
  return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
  let result = []

  while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }

  while (left.length) result.push(left.shift())
  while (right.length) result.push(right.shift())

  return result
}

// var arr = [3, 5, 7, 1, 4, 56, 12, 78, 25, 0, 9, 8, 42, 37]
// var arr = [9, 8, 7, 6, 5, 4, 3, 2, 10]
var arr = [9, 5, 2, 10, 7]

// mergeSort([9, 5, 2, 10, 7])
// merge(mergeSort([9, 5]), mergeSort([2, 10, 7]))
// merge(
//   merge(
//     mergeSort([9]), mergeSort([5])
//     ),
//   merge(
//     mergeSort([2]), mergeSort([10,7])
//     )
//   )

// merge(
//   merge(
//     mergeSort([9]), mergeSort([5])
//     ),
//   merge(
//     mergeSort([2]),merge(
//       mergeSort([10]), mergeSort([7])
//       )
//     )
//   )

// merge(
//   merge(
//    [9],[5]
//     ),
//   merge(
//     mergeSort([2]),merge(
//       [10], [7]
//       )
//     )
//   )

// merge([5,9],
//   merge(
//     mergeSort([2]),[7,10]
//     )
//   )

//   merge([5,9],
// merge(
//   [2],[7,10]
//   )
// )

// merge([5,9],
//  [2,7,10]
//   )

//   merge([5,9],
//  [2,7,10]
//   )

// [2,5,7,9,10]

function merge(left, right) {
  let result = []

  while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }

  while (left.length) result.push(left.shift())
  while (right.length) result.push(right.shift())

  return result
}

var res = mergeSort(arr)
// console.log('res-')
// console.log(res)
